/*
Copyright (C) 2001, 2006 United States Government
as represented by the Administrator of the
National Aeronautics and Space Administration.
All Rights Reserved.
*/
package gov.nasa.worldwind.render;

import gov.nasa.worldwind.WorldWind;
import gov.nasa.worldwind.cache.MemoryCache;
import gov.nasa.worldwind.geom.*;
import gov.nasa.worldwind.globes.Globe;
import gov.nasa.worldwind.terrain.SectorGeometry;
import gov.nasa.worldwind.util.Logging;
import gov.nasa.worldwind.util.RestorableSupport;
import gov.nasa.worldwind.util.measure.AreaMeasurer;

import javax.media.opengl.GL;
import javax.media.opengl.glu.GLU;
import javax.media.opengl.glu.GLUtessellator;
import javax.media.opengl.glu.GLUtessellatorCallback;
import java.awt.*;
import java.util.ArrayList;

/**
 * @author Jim Miller
 * @version $Id: ConformingPolygon.java 7671 2008-12-08 00:18:14Z jmiller $
 */

public class ConformingPolygon extends ConformingShape
{
    /**
     * Instances of class ConvexPartition will normally store triangulated pieces of a
     * polygon as generated by the glu tessellation interface.  If a given shape
     * (probably an instance of a subclass of ConformingPolygon such as
     * ConformingEllipticalPolygon)
     * is known to be convex, then the instance can simply be created with the
     * defining LatLon vertices without using the glu tessellator. In this case,
     * the ConformingPolygon will have only one associated ConvexPartition instance.
     */
    private static class ConvexPartition
    {
        private Sector              bounds;
        private ArrayList<LatLon>   llVerts;
        private final int[]         originalVertexIndex;
        private Plane[]             boundingPlanes;

        private final int           serialNumber;

        public ConvexPartition(Globe globe, ArrayList<LatLon> v, int[] originalVertexIndex)
        {
            llVerts = v;
            if (originalVertexIndex == null)
                this.originalVertexIndex = null;
            else
            {
                this.originalVertexIndex = new int[originalVertexIndex.length];
                System.arraycopy(originalVertexIndex,0,this.originalVertexIndex,0,originalVertexIndex.length);
            }
            computeBoundsAndPlanes(globe);
            this.serialNumber = ConformingShape.getUniqueSerialNumber();
        }

        private void computeBoundsAndPlanes(Globe globe)
        {
            double minLat = llVerts.get(0).getLatitude().radians;
            double maxLat = minLat;
            double minLon = llVerts.get(0).getLongitude().radians;
            double maxLon = minLon;
            Vec4[] xyzVerts = new Vec4[llVerts.size()];
            xyzVerts[0] = globe.computePointFromPosition(
                    llVerts.get(0).getLatitude(),llVerts.get(0).getLongitude(),0);
            for (int i=1 ; i<llVerts.size() ; i++)
            {
                double lat_i = llVerts.get(i).getLatitude().radians;
                if (lat_i < minLat) minLat = lat_i;
                else if (lat_i > maxLat) maxLat = lat_i;
                double lon_i = llVerts.get(i).getLongitude().radians;
                if (lon_i < minLon) minLon = lon_i;
                else if (lon_i > maxLon) maxLon = lon_i;
                xyzVerts[i] = globe.computePointFromPosition(
                        llVerts.get(i).getLatitude(),llVerts.get(i).getLongitude(),0);
            }
            bounds = Sector.fromRadians(minLat,maxLat,minLon,maxLon);
            // We need an initial pass through the vertices to look for edges of constant
            // latitude. For shapes wih a small number of edges (less than 10 or 20 or so),
            // these can be pretty reliably found in the course of the loop that actually builds
            // the planes. However, for shapes with large numbers of edges (e.g., an Ellipse
            // approximated with 100 or more vertices), finding the opposite pair of edges of
            // constant latitude is much more difficult to do reliably in a single pass through
            // the vertex list. This could be handled directly and analytically in a variety of
            // ways in the ConformingEllipticalPolygon class, but ConformingShape instances may also be
            // created directly, and such shapes may exhibit the same issue. Hence a more
            // general approach is needed. What we do here is to make one pass through the
            // vertex list to find the two opposing edges nearest to being horizontal (i.e.,
            // constant latitude).  Since we know the partition here is convex, there can be at
            // most two of them.
            double min1 = 99999.99, min2 = 99999.99; // the two smallest values
            int min1Loc=-1, min2Loc=-1; // the indices of the two smallest values
            for (int i=0 ; i<llVerts.size() ; i++)
            {
                double curDiff = Math.abs(llVerts.get(i).getLatitude().radians -
                    llVerts.get((i+1)%llVerts.size()).getLatitude().radians);
                // establish and maintain the invariants:
                // 1. min1Loc refers to a slot with a minimum local difference
                // 2. min2Loc is at least one slot away from min1Loc -AND- it
                //    also refers to a slot with a minimum local difference
                if (min1Loc < 0)
                {
                    min1Loc = i; min1 = curDiff;
                }
                else if (curDiff < min1)
                {
                    if (i != (min1Loc+1))
                    {
                        min2Loc = min1Loc; min2 = min1;
                    }
                    min1Loc = i; min1 = curDiff;
                }
                else if (i != (min1Loc+1))
                    if ((min2Loc < 0) || (curDiff < min2))
                    {
                        min2Loc = i; min2 = curDiff;
                    }
            }
            if (min1 > ConformingPolygon.constantLatitudeToleranceInRadians)
                // not really an edge of constant latitude
                min1Loc = -1;
            if (min2 > ConformingPolygon.constantLatitudeToleranceInRadians)
                // not really an edge of constant latitude
                min2Loc = -1;
            // Use the initial xyz vertex coordinates to compute the
            // bounding planes. For edges of constant latitude, the planes pass
            // through a point on the y-axis and have normal=(0,1,0). All others
            // pass through the origin of the globe -- (0,0,0) -- and have outward
            // pointing normals determined by cross products of adjacent points.
            boundingPlanes = new Plane[llVerts.size()];
            int jump = llVerts.size() / 2;
            if (jump < 2) jump = 2;
            for (int i=0 ; i<llVerts.size() ; i++)
            {
                Plane plane;
                if ((i == min1Loc) || (i == min2Loc))
                {
                    // constant latitude edge
                    Vec4 p = globe.computePointFromPosition(llVerts.get(i).getLatitude(),llVerts.get(i).getLongitude(),0);
                    plane = new Plane(0,1,0,-p.getY());
                }
                else
                {
                    Vec4 n = xyzVerts[i].cross3(xyzVerts[(i+1)%llVerts.size()]).normalize3();
                    plane = new Plane(n.getX(),n.getY(),n.getZ(),0);
                }

                // make sure the planes all have the vertices
                // in their negative half space.
                if (plane.dot(xyzVerts[(i+jump)%llVerts.size()]) > 0.0)
                {
                    Vec4 n = plane.getNormal();
                    double d = plane.getDistance();
                    plane = new Plane(-n.getX(),-n.getY(),-n.getZ(),-d);
                }
                boundingPlanes[i] = plane;
            }
        }

        Plane[] getBoundingPlanes() { return boundingPlanes; }

        Sector[] getSector()
        {
            if (bounds.getMaxLongitude().degrees-bounds.getMinLongitude().degrees < 180.0)
            {
                Sector[] one = { bounds };
                return one;
            }
            Sector[] two = new Sector[2];
            two[0] = Sector.fromDegrees(bounds.getMinLatitude().degrees, bounds.getMaxLatitude().degrees,
                -180.0,bounds.getMinLongitude().degrees);
            two[1] = Sector.fromDegrees(bounds.getMinLatitude().degrees, bounds.getMaxLatitude().degrees,
                bounds.getMaxLongitude().degrees,180.0);
            return two;
        }

        void update(Globe globe, ArrayList<LatLon> v)
        {
            if (originalVertexIndex != null)
                for (int i=0 ; i<llVerts.size() ; i++)
                    llVerts.set(i,v.get(originalVertexIndex[i]));
            // else the vertices were in one single list and have already been
            // updated, hence we just need to do:
            computeBoundsAndPlanes(globe);
        }
    } // end class ConvexPartition

    private static class CachedShapeDescription
    {
        ArrayList<SectorGeometry.ExtractedShapeDescription> esdL;
        CachedShapeDescription(ArrayList<SectorGeometry.ExtractedShapeDescription> esdL)
        {
            this.esdL = esdL;
        }
    }

    private ArrayList<LatLon>           originalVertices = new ArrayList<LatLon>();
    private ArrayList<ConvexPartition>  partitions = new ArrayList<ConvexPartition>();
    private boolean                     rebuildPartitions = true;
    protected Globe                     globe;
    private boolean                     tessellateContour;

    private AreaMeasurer                areaMeasurer = null;

    private static double constantLatitudeToleranceInDegrees = 0.0001;
    private static double constantLatitudeToleranceInRadians = Math.toRadians(constantLatitudeToleranceInDegrees);

    // need a glu to do the tessellation
    private static GLU glu;
    static
    {
        glu = new GLU();
    }

    /**
     * A Renderable polygon shape defined by a list of LatLon
     *
     * @param g the globe
     * @param vertices the list of LatLon positions that makes the polygon
     */
    public ConformingPolygon(Globe g, Iterable<? extends LatLon> vertices)
    {
        this(g, vertices, null, null);
    }

    /**
     * A Renderable polygon shape defined by a list of LatLon
     *
     * @param g the globe
     * @param vertices   the list of LatLon positions that makes the polygon
     * @param fillColor   the interior fill color
     * @param borderColor the border color
     */
    public ConformingPolygon(Globe g, Iterable<? extends LatLon> vertices, Color fillColor, Color borderColor)
    {
        this(g, vertices, fillColor, borderColor,true);
    }

    protected ConformingPolygon(Globe g, Iterable<? extends LatLon> vertices,
                                Color fillColor, Color borderColor, boolean tessellateContour)
    {
        super(fillColor,borderColor);
        this.globe = g;
        if (vertices == null)
        {
            String message = Logging.getMessage("nullValue.PositionsListIsNull");
            Logging.logger().severe(message);
            throw new IllegalArgumentException(message);
        }
        this.tessellateContour = tessellateContour;
        setOriginalVertices(vertices);
    }

    private boolean externalEdge(ConvexPartition curPartition, Vec4 v1, Vec4 v2)
    {
        if (this.partitions.size() == 1)
            // all edges are external if there is only one partition
            return true;
        double maxC = Math.max(v1.x,Math.max(v1.y,v1.z));
        maxC = Math.max(maxC, Math.max(v2.x,Math.max(v2.y,v2.z)));
        final double tol = 0.00001 * maxC;
        for (ConvexPartition partition : this.partitions)
        {
            if (partition == curPartition)
                continue;
            boolean insideThisPartition = true;
            for (Plane p : partition.boundingPlanes)
                if ( (p.dot(v1) > tol) || (p.dot(v2) > tol) )
                {
                    insideThisPartition = false; break;
                }
            if (insideThisPartition)
                return false;
        }
        return true;
    }

    public Position getReferencePosition()
    {
        return new Position(originalVertices.get(0),0);
    }

    protected void invalidateCache()
    {
        MemoryCache partitionCache = WorldWind.getMemoryCache(CONFORMINGSHAPE_CACHE_KEY);
        for (ConvexPartition partition : this.partitions)
            partitionCache.remove( new CacheKey(this.getClass(), partition.getSector(), partition.serialNumber) );
        areaMeasurer = null;
    }

    public void moveTo(Position position)
    {
        invalidateCache();
        LatLon oldRef = this.getReferencePosition();

        for (int i = 0; i < this.originalVertices.size(); i++)
        {
            LatLon p = this.originalVertices.get(i);
            double distance = LatLon.greatCircleDistance(oldRef, p).radians;
            double azimuth = LatLon.greatCircleAzimuth(oldRef, p).radians;
            LatLon pp = LatLon.greatCircleEndPosition(position, azimuth, distance);
            this.originalVertices.set(i, pp);
        }
        for (ConvexPartition partition : this.partitions)
            partition.update(this.globe,this.originalVertices);
    }

    protected boolean renderInterior(DrawContext dc, GL gl)
    {
        if (globe == null)
            globe = dc.getGlobe();
        if (rebuildPartitions)
            // probably just did a restoreState
            createPartitions();
        float[] colorArray = new float[4];
        MemoryCache partitionCache = WorldWind.getMemoryCache(CONFORMINGSHAPE_CACHE_KEY);
        boolean foundIntersectingPartition = false;
        if (drawInterior || drawBorder) // make sure cache up to date
        {
            for (ConvexPartition partition : this.partitions)
            {
                CacheKey key = new CacheKey(this.getClass(),partition.getSector(), partition.serialNumber);
                CachedShapeDescription csd = (CachedShapeDescription)partitionCache.getObject(key);
                ArrayList<SectorGeometry.ExtractedShapeDescription> esdL = null;
                if (csd != null) esdL = csd.esdL;
                if ((esdL == null) || isExpired(dc))
                {
                    if (esdL != null)
                    {
                        partitionCache.remove(key);
                        esdL = null;
                    }
                    Plane[] partitionPlanes = partition.getBoundingPlanes();
                    Sector[] partitionSector = partition.getSector();
                    for (SectorGeometry sg : dc.getSurfaceGeometry())
                    {
                        boolean proceed = false;
                        for (Sector s : partitionSector)
                            if (sg.getSector().intersects(s))
                            {
                                proceed = true; break;
                            }
                        if (proceed)
                        {
                            SectorGeometry.ExtractedShapeDescription sgPolygons =
                                sg.getIntersectingTessellationPieces(partitionPlanes);
                            if (sgPolygons != null)
                            {
                                if (esdL == null)
                                    esdL = new ArrayList<SectorGeometry.ExtractedShapeDescription>(4);
                                esdL.add(sgPolygons);
                                foundIntersectingPartition = true;
                            }
                        }
                    }
                    if (esdL != null)
                        partitionCache.add(key, new CachedShapeDescription(esdL), sizeInBytesOf(esdL));
                }
                if ( (esdL != null) && drawInterior)
                    for (SectorGeometry.ExtractedShapeDescription esd : esdL)
                        for (Vec4[] sgT : esd.interiorPolys)
                        {
                            if (!dc.isPickingMode())
                                gl.glColor4fv(fillColor.getComponents(colorArray),0);
                            gl.glBegin(GL.GL_POLYGON);
                            for (Vec4 v : sgT)
                                gl.glVertex3d(v.getX(),v.getY(),v.getZ());
                            gl.glEnd();
                        }
            }
            updateExpiryCriteria(dc);
        }
        return foundIntersectingPartition;
    }

    protected void renderBoundary(DrawContext dc, GL gl, boolean knownToBeVisible)
    {
        if (globe == null)
            globe = dc.getGlobe();
        if (rebuildPartitions)
            // probably just did a restoreState
            createPartitions();
        if (!knownToBeVisible)
        {
            // the shape may or may not be visible; knownToBeVisible could be
            // false here either because we are not drawing the interiors, or
            // because we extracted data from the cache.
            for (ConvexPartition partition : this.partitions)
            {
                Sector[] partitionSector = partition.getSector();
                for (SectorGeometry sg : dc.getSurfaceGeometry())
                {
                    for (Sector s : partitionSector)
                        if (sg.getSector().intersects(s))
                        {
                            knownToBeVisible = true;
                            break;
                        }
                    if (knownToBeVisible)
                        break;
                }
                if (knownToBeVisible)
                    break;
            }
        }
        if (drawBorder && knownToBeVisible)
        {
            float[] colorArray = new float[4];
            if (!dc.isPickingMode())
                gl.glColor4fv(borderColor.getComponents(colorArray),0);
            MemoryCache partitionCache = WorldWind.getMemoryCache(CONFORMINGSHAPE_CACHE_KEY);
            for (ConvexPartition partition : this.partitions)
            {
                CacheKey key = new CacheKey(this.getClass(),partition.getSector(), partition.serialNumber);
                CachedShapeDescription csd = (CachedShapeDescription)partitionCache.getObject(key);
                ArrayList<SectorGeometry.ExtractedShapeDescription> esdL = null;
                if (csd != null) esdL = csd.esdL;
                if (esdL != null)
                    for (SectorGeometry.ExtractedShapeDescription esd : esdL)
                    {
                        gl.glBegin(GL.GL_LINES);
                        for (SectorGeometry.BoundaryEdge be : esd.shapeOutline)
                        {
                            Vec4 v1 = be.vertices[be.i1];
                            Vec4 v2 = be.vertices[be.i2];
                            if (externalEdge(partition,v1,v2))
                            {
                                gl.glVertex3d(v1.x,v1.y,v1.z);
                                gl.glVertex3d(v2.x,v2.y,v2.z);
                            }
                        }
                        gl.glEnd();
                    }
            }
        }
    }

    protected void setOriginalVertices(Iterable<? extends LatLon> vertices)
    {
        // This protected method assumes that the convexity/concavity has not changed.
        // Note that it uses "this.tessellateContour" as set by the constructor!
        this.originalVertices.clear();
        // the last vertex is a copy of the first, but that confuses the
        // various pieces of the tessellation logic. We therefore ignore the
        // first vertex here.
        boolean first = true;
        for (LatLon ll : vertices)
        {
            if (first)
                first = false;
            else
                this.originalVertices.add(ll);
        }
        createPartitions();
    }

    private void createPartitions()
    {
        this.partitions.clear();
        if (this.tessellateContour && (originalVertices.size() > 3))
            // use the glu tessellator to create triangles defining the shape.
            tessellate();
        else
            partitions.add( new ConvexPartition(globe,originalVertices,null) );
        this.rebuildPartitions = false;
    }

    protected void doGetRestorableState(RestorableSupport rs, RestorableSupport.StateObject context)
    {
        if (this.originalVertices != null)
            rs.addStateValueAsLatLonList(context, "locations", this.originalVertices);
        rs.addStateValueAsBoolean(context, "tessellateContour", this.tessellateContour);
    }

    protected void doRestoreState(RestorableSupport rs, RestorableSupport.StateObject context)
    {
        ArrayList<LatLon> locations = rs.getStateValueAsLatLonList(context, "locations");
        if (locations != null)
            this.originalVertices = locations;
        Boolean tess = rs.getStateValueAsBoolean(context, "tessellateContour");
        if (tess != null)
            this.tessellateContour = tess.booleanValue();
        // force following to be recomputed at the next opportunity
        this.rebuildPartitions = true;
        this.globe = null;
    }

    public double getLength(Globe globe)
    {
        if (areaMeasurer == null)
            makeAreaMeasurer();
        return areaMeasurer.getLength(globe);
    }

    public double getArea(Globe globe)
    {
        if (areaMeasurer == null)
            makeAreaMeasurer();
        return areaMeasurer.getArea(globe);
    }

    public double getPerimeter(Globe globe)
    {
        if (areaMeasurer == null)
            makeAreaMeasurer();
        return areaMeasurer.getPerimeter(globe);
    }

    public double getWidth(Globe globe)
    {
        if (areaMeasurer == null)
            makeAreaMeasurer();
        return areaMeasurer.getWidth(globe);
    }

    public double getHeight(Globe globe)
    {
        if (areaMeasurer == null)
            makeAreaMeasurer();
        return areaMeasurer.getHeight(globe);
    }

    private void makeAreaMeasurer()
    {
        ArrayList<Position> positions = new ArrayList<Position>(originalVertices.size() + 1);
        for (LatLon ll : originalVertices)
            positions.add(new Position(ll.getLatitude(),ll.getLongitude(),0.0));
        positions.add(positions.get(0));
        areaMeasurer = new AreaMeasurer(positions);
        areaMeasurer.setFollowTerrain(true);
    }

    private void tessellate()
    {
        TessCallback tcb = new TessCallback(partitions,globe);
        GLUtessellator theTess = glu.gluNewTess();
        glu.gluTessCallback(theTess,GLU.GLU_TESS_BEGIN,tcb);
        glu.gluTessCallback(theTess,GLU.GLU_TESS_VERTEX,tcb);
        glu.gluTessCallback(theTess,GLU.GLU_TESS_END,tcb);

        glu.gluTessBeginPolygon(theTess, null);
        glu.gluTessBeginContour(theTess);
        int i = 0;
        for (LatLon ll : this.originalVertices)
        {
            double[] xyz = { 0.0, 0.0, 0.0 };
            xyz[0] = ll.getLongitude().radians;
            xyz[1] = ll.getLatitude().radians;
            TaggedLatLonVertex tLLV = new TaggedLatLonVertex(ll,i);
            glu.gluTessVertex(theTess,xyz,0,tLLV);
            i++;
        }
        glu.gluTessEndContour(theTess);
        glu.gluTessEndPolygon(theTess);
    }

    private static class TaggedLatLonVertex
    {
        public TaggedLatLonVertex(LatLon ll, int i) { this.ll = ll; this.ll_index = i; }
        public LatLon   ll;
        public int      ll_index;
    }

    private static class TessCallback implements GLUtessellatorCallback
    {
        private int                         beginType;
        private ArrayList<ConvexPartition>  partitions;
        private Globe                       globe;

        private TaggedLatLonVertex[]        workingStore;
        private int                         nextWSLoc;

        public TessCallback(ArrayList<ConvexPartition> partitions, Globe globe)
        {
            this.beginType = -1;
            this.partitions = partitions;
            this.globe = globe;
            this.workingStore = new TaggedLatLonVertex[3];
            this.nextWSLoc = 0;
        }

        public void begin(int type) { beginType = type; nextWSLoc = 0; }

        public void beginData(int type, Object polygonData) {}

        public void combine(double[] coords, Object[] data, float[] weight, Object[] outData) {}

        public void combineData(double[] coords, Object[] data, float[] weight, Object[] outData, Object polygonData) {}

        public void edgeFlag(boolean boundaryEdge) {}

        public void edgeFlagData(boolean boundaryEdge, Object polygonData) {}

        public void end() { beginType = nextWSLoc = -1; }

        public void endData(Object polygonData) {}

        public void error(int errnum) {}

        public void errorData(int errnum, Object polygonData) {}

        public void vertex(Object vertexData)
        {
            TaggedLatLonVertex tLLV = (TaggedLatLonVertex)vertexData;
            workingStore[nextWSLoc++] = tLLV;
            if (nextWSLoc == 3)
            {
                ArrayList<LatLon> loc = new ArrayList<LatLon>(3);
                loc.add(workingStore[0].ll); loc.add(workingStore[1].ll); loc.add(workingStore[2].ll);
                int[] index = { workingStore[0].ll_index, workingStore[1].ll_index, workingStore[2].ll_index };
                partitions.add( new ConvexPartition(globe,loc,index) );

                switch (beginType)
                {
                    case GL.GL_TRIANGLE_FAN:
                        workingStore[1] = workingStore[2];
                        nextWSLoc = 2;
                        break;
                    case GL.GL_TRIANGLE_STRIP:
                        workingStore[0] = workingStore[1];
                        workingStore[1] = workingStore[2];
                        nextWSLoc = 2;
                        break;
                    case GL.GL_TRIANGLES:
                        nextWSLoc = 0;
                        break;
                    default:
                }
            }
        }

        public void vertexData(Object vertexData, Object polygonData) {}
    }
}